package medium目标和;

import org.testng.annotations.Test;

import java.util.ArrayList;
import java.util.List;

public class Solution {



    //动态规划
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        int diff = sum - target;
        if (diff < 0 || diff % 2 != 0) {  // diff%2 == 0 neg = (sum-target)/2
                                          // neg = sum 和里面要变成负数的和
            return 0;
        }
        int neg = diff / 2;
        int[] dp = new int[neg + 1];
        dp[0] = 1;
        for (int num : nums) {
            for (int j = neg; j >= num; j--) {
                dp[j] += dp[j - num];
            }
        }
        return dp[neg];
    }

    //回溯
    int num = 0;
    public int findTargetSumWays2(int[] nums, int target) {
        int n = nums.length;
        test(nums, 0, n-1, 0, target);
        return num;
    }
    public void test(int[] nums, int i, int n, int sum, int target){
        if (i>n){
            if (sum == target){
                num++;
            }
            return;
        }
        else {
            test(nums, i+1, n,sum-nums[i], target );
            test(nums, i+1, n,sum+nums[i], target );
        }

    }

    //暴力
    public int findTargetSumWays1(int[] nums, int target) {
        int num = 0;
        int n = nums.length;
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (list.isEmpty()){
                list.add(nums[i]);
                list.add(-nums[i]);
            }
            else {
                List<Integer> list1 = new ArrayList<>();
                for (int j:
                        list) {
                    list1.add(j+nums[i]);
                    list1.add(j-nums[i]);
                }
                list = new ArrayList<>(list1);
            }
        }
        for (int i:
                list) {
            if (i == target){
                num++;
            }
        }
        return num;
    }

    @Test
    public void findTargetSumWays() {
        int target = 1;
        int[] nums = {1,1,1,1,1};
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        int diff = sum - target;
        if (diff < 0 || diff % 2 != 0) {
            System.out.println(0);
        }
        int n = nums.length, neg = diff / 2;
        int[][] dp = new int[n + 1][neg + 1];
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            int num = nums[i - 1];
            for (int j = 0; j <= neg; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= num) {
                    dp[i][j] += dp[i - 1][j - num];
                }
            }
        }
        for (int i = 0; i < n+1; i++) {
            for (int j = 0; j < neg+1; j++) {
                System.out.printf("  "+dp[i][j]);
            }
            System.out.println();
        }
        System.out.println(dp[n][neg]);
    }
}
